<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 时间O(n^2)
        // 空间O(n) n是dp数组的长度
        // 思路：
        // 1. 关键是找到重叠子问题，n=3时，头结点为3的左子树和n等于2的情况的子树一致
        // 2. 头结点为2时，左右子树都只有一个节点 和 n=1的情况一致
        // 3. 头结点为1时，依然和头结点为2的情况一致
        // 4. n=3 => dp[3] = 1为头结点的元素 + 2为头结点的元素 + 3为头结点的元素
        //    元素1位头结点的元素 = dp[0] * dp[2]
        //    元素2位头结点的元素 = dp[1] * dp[1]
        //    元素3位头结点的元素 = dp[2] * dp[0]
        var numTrees = function (n) {
            debugger
            // 记得创建数组时 要给初始值 不然后续就会变成NaN了
            let dp = new Array(n + 1).fill(0)
            // 必须初始化dp[0] = 1 因为后面的dp[1] 依赖 dp[0]的值
            dp[0] = 1
            for (let i = 1; i <= n; i++) {
                for (let j = 1; j <= i; j++) {
                    dp[i] = dp[i] + dp[j - 1] * dp[i - j]
                }
            }
            return dp[n]
        };
        console.log(numTrees(3));
    </script>
</body>

</html>